package Graph;

import java.util.ArrayList;
import java.util.List;

public class bellmanFord {
    //bellmanFord 单源最短路径(起点只有一个)
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        v1.edges = List.of(new Edge(v3, 1),
                new Edge(v2, 2)
        );
        v2.edges = List.of(new Edge(v3, -2)
        );

        v3.edges = List.of(new Edge(v4, 1)
        );
        v4.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4);
        bellmanford(graph, v1);
    }

    private static void bellmanford(List<Vertex> graph, Vertex source) {
        //起点设置为0
        source.dist = 0;
        int size = graph.size();
        for (int i = 0; i < size - 1; i++) {
            graph.forEach(s -> {
                s.edges.forEach(edge -> {
                    //处理每一条边
                    Vertex e = edge.linked;
                    if (s.dist != Integer.MAX_VALUE && s.dist + edge.weigth < e.dist) {
                        e.prev = s;
                        e.dist = s.dist + edge.weigth;
                    }
                });
            });
        }

        //验证结果
        graph.forEach(v -> {
            System.out.println(v.name + " " + v.dist + " " + (v.prev != null ? v.prev.name : "null"));
        });
    }
}
